package LeetCode;

public class No234 {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null) return true;
        //快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast = fast.next.next;
        }
        ListNode curr = slow.next;
        ListNode pre = null;
        while(curr!=null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr=temp;
        }
        while(head!=null&&pre!=null){
            if(head.val!=pre.val) return false;
            head=head.next;
            pre=pre.next;
        }
        reverse(slow.next);
        return true;

//        StringBuilder sb = new StringBuilder();
//        while(head!=null){
//            sb.append(head.val);
//            head=head.next;
//        }
//        String s = sb.toString();
//        return s.equals(sb.reverse().toString());

//        Deque<Integer> deque = new LinkedList<>();
//        while(head!=null){
//            deque.push(head.val);
//            head=head.next;
//        }
//        while(deque.size()>1){
//            if(deque.getFirst()!=deque.getLast()) return false;
//            deque.removeFirst();
//            deque.removeLast();
//        }
//        return true;
    }

    public ListNode reverse(ListNode head){
        ListNode curr = head;
        ListNode pre = null;
        while(curr!=null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr=temp;
        }
        return pre;
    }
}
